package com.gwcloud.leetcode.tags.backtrace;

/** 
* @ClassName   : Leetcode079 
* @author      : ganwei 
* @date        : 2020年5月8日 
* @Description : Leetcode079 单词搜索 
*/
public class Leetcode0079 {
	/**
	 * -解题思路，继续我的回溯打法
	 */
    public boolean exist(char[][] board, String word) {
    	if(board.length == 0 || word.length() == 0) {
    		return false;
    	}

    	for(int i = 0; i < board.length; i++) {
    		for(int j = 0; j < board[i].length; j++) {
    			if(backtrack(board,word,new boolean[board.length][board[0].length],i,j)) {
    				return true;
    			}
    		}
    	}
    	
    	return false;
    }
    
    /**
     * -回溯主体
     */
    public boolean backtrack(char[][] board, String word, boolean[][] isVisited, int i, int j) {
    	System.out.print(i);
    	System.out.print(' ');
    	System.out.print(j);
    	System.out.print(' ');
    	System.out.print(word);
    	System.out.println();
    	

    	if(word.isEmpty()) {
    		return true;
    	}
    	
    	
    	if(board[i][j] == word.charAt(0)) {
    		isVisited[i][j] = true;
    		if(i+1 >= 0 && i+1 < board.length && !isVisited[i+1][j]) {
    			
    			if(backtrack(board, word.substring(1), isVisited, i+1, j)) {
    				return true;
    			}
    			
    		}
    		if(j+1 >= 0 && j+1 < board[i].length && !isVisited[i][j+1]) {
    			
    			if(backtrack(board, word.substring(1), isVisited, i, j+1)) {
    				return true;
    			}
    			
    		}
    		if(i-1 >= 0 && i-1 < board.length && !isVisited[i-1][j]) {
    			
    			if(backtrack(board, word.substring(1), isVisited, i-1, j)) {
    				return true;
    			}
    			
    		}
    		if(j-1 >= 0 && j-1 < board[i].length && !isVisited[i][j-1]) {
    			
    			if(backtrack(board, word.substring(1), isVisited, i, j-1)) {
    				return true;
    			}
    			
    		}
    		isVisited[i][j] = false;
    		
    	}

    	return false;
    	
    } 
    
    public static void main(String[] args) {
    	Leetcode0079 l079 = new Leetcode0079();
    	char[][] b = {
    			  {'A','B','C','E'},
    			  {'S','F','C','S'},
    			  {'A','D','E','E'}
    			};
    	
    	System.out.println(l079.exist(b,"ABCCED"));
    	String ss = "ganwei";
    
    	ss.substring(1);
    	System.out.println(ss);
    }
}
